# 给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
# 你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
# 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
# 文本的最后一行应为左对齐，且单词之间不插入额外的空格。


class Solution:
    def fullJustify(self, words, maxWidth: int):
        mid_list, n, now_length, res = [], 0, 0, []
        for word in words:
            now_length += (len(word) + 1)
            if now_length == maxWidth + 1:
                mid_list.append(word)
                for i in range(n):
                    mid_list.insert(2*i+1, " ")
                res.append("".join(mid_list))
                mid_list, n, now_length = [], 0, 0
            elif now_length > maxWidth + 1:
                if n > 1:
                    now_length -= (len(word) + 1)
                    len_all_space = maxWidth + n - now_length
                    len_one_space = len_all_space // (n - 1)
                    left_len_space = len_all_space % (n - 1)
                    for i in range(n-1):
                        if i < left_len_space:
                            mid_list.insert(2 * i + 1, " " * (len_one_space + 1))
                        else:
                            mid_list.insert(2 * i + 1, " " * len_one_space)
                    # print(mid_list)
                    res.append("".join(mid_list))
                else:
                    res.append(mid_list[0].ljust(maxWidth))
                mid_list, n, now_length = [word], 1, len(word) + 1
            else:
                mid_list.append(word)
                n += 1
        if n != 0:
            for i in range(n - 1):
                mid_list.insert(2 * i + 1, " ")
            res.append("".join(mid_list).ljust(maxWidth))
        return res


a = Solution()
print(a.fullJustify(["Science", "is", "what", "we", "understand", "well", "enough", "to", "explain",
                     "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do", "so"], maxWidth=20))